package com.itheima.leetcode.od.b.graph.unionfindset;

import java.util.Arrays;

/**
 * 并查集实现
 */
public class UnionFindSet {
    int[] fa;
    int count[]; // 动态规划
    public int connectedCount; // 连通分量数

    public UnionFindSet(int n) {
        this.count = new int[n];
        this.fa = new int[n];
        this.connectedCount = n;
        Arrays.fill(count, 1);
        for (int i = 0; i < n; i++) {
            this.fa[i] = i;
        }
    }

    public int find(int x) {
        if (x != this.fa[x]) {
            return (this.fa[x] = this.find(this.fa[x]));
        }
        return x;
    }

    public void union(int x, int y) {

        int x_fa = this.find(x);
        int y_fa = this.find(y);

        if (x_fa == y_fa) {
            return;
        }

        this.connectedCount--;

        if (this.count[x_fa] < this.count[y_fa]) {
            int t = x_fa;
            x_fa = y_fa;
            y_fa = t;
        }

        this.fa[y_fa] = x_fa;
        this.count[x_fa] = this.count[x_fa] + this.count[y_fa];
    }

    public int getMax() {
        return Arrays.stream(this.count).max().orElse(0);
    }
}
